//
//  main.c
//  MallocTest
//
//  Created by wangrui on 14-11-27.
//  Copyright (c) 2014年 wangrui. All rights reserved.
//

#include <stdio.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <stdlib.h>
#include <unistd.h>

void printLimit()
{
	struct rlimit * limit = (struct rlimit *)malloc(sizeof(struct rlimit));
	
	getrlimit(RLIMIT_AS, limit);
	
	printf("soft limit: %llu, hard limit: %llu\n", limit->rlim_cur, limit->rlim_max);
}

void *simpleMalloc(size_t size)
{
	void *p = sbrk(0); //获取系统break指针
	
	if (p == (void *)-1) {
		return NULL;
	}
	
	return p;
}

/** 测试代码
 *  printLimit();
	
	int *a = (int *)simpleMalloc(sizeof(int));
	*a = 5;
	printf("%d\n",*a);
 */

//#pragma pack(8) //这个要写在结构体定义之前才有用，变化值查看结果 32位系统对齐系数为4 64位系统对齐系数为8.
/*
 *内存对齐测试代码
 *
	printf("%lu\n",sizeof(int));
	printf("%lu\n",sizeof(long));
	printf("%lu\n",sizeof(size_t));
	printf("%lu\n",sizeof(struct s_block));
	printf("%lu\n",sizeof(p_block_t));

	struct s_block s;

	printf("%p\n",&s.a);
	printf("%p\n",&s.size);
	printf("%p\n",&s.next);
	printf("%p\n",&s.free);
	printf("%p\n",&s.padding);
	printf("%p\n",&s.data);
	printf("%p\n",&s.data2);
*/

#pragma mark - implementation malloc

#define BLOCK_SIZE 32 //元数据块需要开辟的长度
void *first_block = NULL;

typedef struct meta_block *p_block;

struct meta_block {
	size_t size;//数据区大小
    p_block prev; //用于解决碎片问题
	p_block next; //下一个块的指针
	int free; //是否空闲
	int padding; //填充值，保持内存对齐
	char data[1]; //虚位,分配的内存数据块的第一个字节,也就是数据的开始
};

//找到第一个符合要求的
p_block find_block(p_block *last,size_t size)
{
	p_block b = first_block;
	
	while (b && !(b->free && b->size >= size)) { //不满足找下一个
		*last = b;
		b = b->next;
	}
	
	return b;
}


//开辟新的blok
p_block extend_heap(p_block last, size_t size)
{
	p_block b = sbrk(0);
	
	if (sbrk(BLOCK_SIZE + size) == (void *)-1) {
		return NULL;
	}
	
	b->size = size;
	b->next = NULL;
	if (last) {
		last->next = b;
        b->prev = last;
	}
	b->free = 0;
	
	return b;
}

void split_block(p_block b,size_t size)
{
	p_block nb = (void *)(b->data + size);
	nb->size = b->size - size - BLOCK_SIZE;
	nb->next = b->next;
	nb->free = 1;
	b->size = size;
	b->next = nb;
}

size_t align8(size_t s) //使数据区分配的内存按8字节对齐
{
	if ((s & 0x7) == 0) {
		return s;
	}
	
	return ((s>>3)+1) << 3;
}

void *m_malloc(size_t size)
{
	p_block b,last;
	size_t s;
	
	s = align8(size);
	
	if (first_block) {
		last = first_block;
		b = find_block(&last, s);
		
		if (b) {
			
			if ((b->size - s) >= (BLOCK_SIZE + 8)) {
				split_block(b, s);
			}
			
			b->free = 0;
		}
		
		else {
			
			b = extend_heap(last, s);
			if (!b) {
				return NULL;
			}
			
		}
		
	}
	else {
		b = extend_heap(NULL, s);
		if (!b) {
			return NULL;
		}
		
		first_block = b;
	}
	
	return b->data;
}

void *m_calloc(size_t number, size_t size)
{
	size_t *new;
	size_t s8,i;
	new = m_malloc(number * size);
	if (new) {
		s8 = align8(number * size) >> 3; //按size_t数组的方式进行0赋值
		for (i=0; i<s8; i++) {
			new[i] = 0;
		}
	}
	
	return new;
}


p_block get_block(void *p)
{
    //按照一个字节移动,移到meta_block开始的地方
    char *tmp = p;
    tmp -= BLOCK_SIZE;
    p = tmp;
    return  p;
}

int valid_addr(void *p)
{
    if (first_block) {
        if (p > first_block && p<sbrk(0)) {
            return p == (get_block(p))->data;
        }
    }
    
    return 0;
}

/**
 *合并碎片
 */
p_block fusion(p_block b)
{
    if (b->next && b->next->free) {
        b->size += BLOCK_SIZE + b->next->size;
        b->next = b->next->next;
        if (b->next) {
            b->next->prev = b;
        }
    }
    
    return b;
}

void m_free(void *p)
{
    p_block b;
    if (valid_addr(p)) {
        b = get_block(p);
        b->free = 1;
        if (b->prev && b->prev->free) {
            b = fusion(b->prev);
        }
        if (b->next) {
            fusion(b);
        }
        else {
            if (b->prev) {
                b->prev->prev = NULL;
            }
            else {
                first_block = NULL;
            }
            
            brk(b);
        }
    }
}


void copy_block(p_block src, p_block dst)
{
    size_t *sdata, *ddata;
    size_t i;
    sdata = (void *)src->data;
    ddata = (void *)dst->data;
    for (i=0; (i*8 < src->size) && (i*8 < dst->size); i++) {
        ddata[i] = sdata[i];
    }
}

void * m_realloc(void *p,size_t size)
{
    size_t s;
    p_block b,new;
    void *newp;
    if (!p) {
        return m_malloc(size);
    }
    
    if (valid_addr(p)) {
        s = align8(size);
        b = get_block(p);
        if (b->size >= s) {
            if (b->size-s >= (BLOCK_SIZE + 8)) {
                split_block(b, s);
            }
        }
        else {
            //是否可以进行合并
            if(b->next && b->next->free && (b->size + b->next->size + BLOCK_SIZE) >= s)
            {
                fusion(b);
            }
            
            if (b->size - s >= (BLOCK_SIZE + 8))
            {
                split_block(b, s);
            }
            else
            {
                //新分配
                newp = m_malloc(s);
                if(!newp)
                    return NULL;
                new = get_block(newp);
                copy_block(b,new);
                m_free(p);
                return newp;
            }
        }
        
        return p;
    }
    
    return NULL;
}


#pragma mark - main

int main(int argc, const char * argv[]) {
	
    int *a = m_calloc(1, 8);
    *a = 5;
    printf("%d\n",*a);
    
    m_free(a);
    
    
    return 0;
}
